#include <bits/stdc++.h>

using namespace std;

#define MAXV 100
#define INF 0x3f3f3f3f

// 深度优先遍历的实现与测试
// 邻接表

// 边节点
typedef struct ArcNode{
	int adjvex;  // 邻接点的序号
	int weight;  // 连接邻接点边的权重
	struct ArcNode * nextarc;
} ArcNode;

// 头结点
typedef struct VNode{
	// 头结点的其它信息
	ArcNode * firstarc;
}VNode;

typedef struct {
	VNode adjlist[MAXV];
	int n,e;  // 统计结点和边的数目
}AdjGraph;

int visited[MAXV] = {0};

// 深度优先遍历算法
void DFS(AdjGraph * G , int v){
	ArcNode * p; // 定义临时变量的边节点 
	visited[v] = 1;

	printf("%d",v);

	// 邻接表采用头插法构造链表，但这里是搜索算法不需要构造链表
	p = G->adjlist[v].firstarc;
	while(p != NULL){
		if(visited[p->adjvex] == 0){
			DFS(G,p->adjvex);  // 构造递归树是比较容易理解递归执行过程的方法
		}
		p = p->nextarc;
	}
}
// 辅助函数：打印邻接表
void printAdjGraph(AdjGraph *G) {
    cout << "邻接表:" << endl;
    for(int i = 0; i < G->n; i++) {
        cout << "顶点" << i << ": ";
        ArcNode *p = G->adjlist[i].firstarc;
        while(p != NULL) {
            cout << "(" << p->adjvex << "," << p->weight << ") ";
            p = p->nextarc;
        }
        cout << endl;
    }
}
// 辅助函数：创建邻接表

// 初始化邻接表
void initAdjGraph(AdjGraph * &G, int n) {
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    G->n = n;
    G->e = 0;
    for(int i = 0; i < n; i++) {
        G->adjlist[i].firstarc = NULL;
    }
}

// 向邻接表添加边
void addEdge(AdjGraph *&G, int u, int v, int weight) {
    // 创建新的边节点
    ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
    p->adjvex = v;
    p->weight = weight;
    p->nextarc = G->adjlist[u].firstarc;  // 头插法
    G->adjlist[u].firstarc = p;
    G->e++;
}


// 图结构说明函数（帮助于理解图的连接关系）
void explainGraphStructure() {
    cout << "图结构说明:" << endl;
    cout << "顶点0连接到: 1(权重8)、3(权重5)" << endl;
    cout << "顶点1连接到: 2(权重3)" << endl;
    cout << "顶点2连接到: 4(权重6)" << endl;
    cout << "顶点3连接到: 2(权重9)" << endl;
    cout << "顶点4没有出边" << endl << endl;
}
// 完整DFS遍历（处理有向图，确保所有节点都被访问）
void completeDFS(AdjGraph * G) {
    // 重置访问标记
    memset(visited, 0, sizeof(visited));
    
    cout << "完整DFS遍历所有节点: ";
    // 遍历所有顶点，对未访问的顶点调用DFS
    for(int i = 0; i < G->n; i++) {
        if(visited[i] == 0) {
            DFS(G, i);
        }
    }
    cout << endl;
}
// 主测试用例：特定连通图  有向图
// 
// 当 DFS 结束后检查是否还有未访问的节点，若有则从这些未访问节点开始继续 DFS，直到所有节点都被访问
void testCase() {
    cout << "=== 测试用例：特定连通图的DFS遍历 ===" << endl;
    AdjGraph *G;
    initAdjGraph(G, 5);  // 创建5个顶点的图   函数传参都是值传递，输出型参数用引用传递
    
    // 添加边（按照题目中提供的数据）
    addEdge(G, 0, 1, 8);
    addEdge(G, 0, 3, 5);
    addEdge(G, 1, 2, 3);
    addEdge(G, 2, 4, 6);
    addEdge(G, 3, 2, 9);
    
    // 打印图结构信息
    explainGraphStructure();
    printAdjGraph(G);
    
    // 从顶点0开始DFS遍历
    cout << "从顶点1开始的DFS遍历: ";
    DFS(G, 1);
    cout << endl << endl;
    
    // 完整DFS遍历（确保所有节点都被访问）
    completeDFS(G);
    // // 从顶点2开始的DFS遍历（额外测试）
    // cout << "从顶点2开始的DFS遍历: ";
    // DFS(G, 2);
    // cout << endl;
}




int main() {
    testCase();
    return 0;
}